import System.IO
import Data.List

main :: IO ()
main = do
    n <- readInt "Grid size: " validGridSize
    grid <- gameLoop (blankGrid n) n X
    putStrLn (gridToStr grid)
    putStrLn $ "winner: " ++ show (getWinner grid n)
    where validGridSize i = i >= 3 && i < 11

gameLoop :: Grid -> Int -> Mark -> IO Grid
gameLoop grid n player = do
    putStrLn (gridToStr grid)
    index <- readInt ("Player " ++ show player ++ " select (0-" ++ show ((n * n) - 1) ++ "): ") validPick
    hFlush stdout 
    let (row, col) = (div index n, mod index n)
    let newgrid = setPlace grid row col player
    if hasWinner newgrid n || isFull newgrid
        then return newgrid
        else gameLoop newgrid n (other player)
    where validPick i = i >= 0 && i < n && not (isTaken grid (div i n) (mod i n))

readInt :: String -> (Int -> Bool) -> IO Int
readInt prompt acceptable = do
    putStrLn prompt
    line <- getLine
    if isInteger line then parseAndCheck line else err
    where err = do
              putStrLn "Invalid"
              readInt prompt acceptable
          parseAndCheck s = let intValue = read s :: Int in
               if acceptable intValue
                    then return intValue
                    else err

isInteger :: String -> Bool
isInteger s = case reads s :: [(Integer, String)] of
    [(_, "")] -> True
    _         -> False

gridToStr :: Grid -> String
gridToStr grid = intercalate "\n" (map show grid)

data Mark = X | O | Blank deriving (Eq)

other :: Mark -> Mark
other X = O
other O = X
other Blank = Blank

instance Show Mark where
    show X = "X"
    show O = "O"
    show Blank = "_"

type Grid = [[Mark]]

blankGrid :: Int -> Grid
blankGrid n = replicate n $ replicate n Blank

setPlace :: Grid -> Int -> Int -> Mark -> Grid
setPlace grid row col mark = replaceNth (replaceNth mark col (grid !! row)) row grid
    where replaceNth y 0 (_:xs) = y:xs
          replaceNth y i (x:xs) = x:replaceNth y (i-1) xs
          replaceNth _ _ _ = []

getPlace :: Grid -> Int -> Int -> Mark
getPlace grid row col = (grid !! row) !! col

isTaken :: Grid -> Int -> Int -> Bool
isTaken grid row col = getPlace grid row col /= Blank

isFull :: Grid -> Bool
isFull grid = not . or $ map (== Blank) (concat grid)

getWinner :: Grid -> Int -> Mark
getWinner grid n
    | isWinner grid n X = X
    | isWinner grid n O = O
    | otherwise = Blank

hasWinner :: Grid -> Int -> Bool
hasWinner grid n = Blank /= getWinner grid n

isWinner :: Grid -> Int -> Mark -> Bool
isWinner grid n mark = or $ map (checkN getCol) [0..n-1] ++ map (checkN getRow) [0..n-1] ++ [check getDiag1] ++ [check getDiag2]
    where checkN f x = allEqual mark $ f x
          check = allEqual mark
          allEqual y (x:xs) = y == x && allEqual y xs
          allEqual _ [] = True
          getRow row = getN (zip (replicate n row) [0..n-1])
          getCol col = getN (zip [0..n-1] (replicate n col))
          getDiag1 = getN (zip [0..n-1] [0..n-1])
          getDiag2 = getN (zip [0..n-1] (reverse [0..n-1]))
          getN coords = let getAt (row, col) = getPlace grid row col in map getAt coords